#include "tools.h"

// 二叉树先序遍历
void quicksort(int arr[], int left, int right){
    // 递归基
    if(left >= right) return;

    // 做事：捡出两侧元素 + 基准归位
    int base = left;
    int p1 = left + 1, p2 = right;
    while(p1 < p2){
        while(p1 < p2 && arr[base] <= arr[p2]) --p2; // ！先右后左，非常重要
        while(p1 < p2 && arr[p1] <= arr[base]) ++p1;
        if(p1 < p2)
            swap(arr[p1], arr[p2]);
    }
    if(arr[p1] < arr[base]) swap(arr[p1], arr[base]);

    quicksort(arr, left, p1 - 1);
    quicksort(arr, p1 + 1, right);
}

int main(int argc, char const *argv[])
{
    int arr[] = {6, 2, 1, 7, 9, 3, 4, 5, 10, 8};

    quicksort(arr, 0, 9);

    show(arr, 10);

    return 0;
}
